 /**
 * @file array_list.c
 * File implementing a generic ArrayList data structure
 * @author Denis Ollier
 * @ingroup ArrayList
 */

#include <array_list.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/**
 * Calculates the increment value which must be applied to increase the array capacity
 * @param list
 * @param needed_increment
 * @return
 * @todo Test the function.
 */
static unsigned int array_list_calculate_increment(array_list list, unsigned int needed_increment);

/**
 * Compares two elements of the ArrayList.
 * @param list
 * @param element1
 * @param element2
 * @retval -1
 * @retval 0
 * @retval 1
 * @todo Test the function.
 */
static unsigned int array_list_compare_elements(array_list list, const void* element1, const void* element2);

/**
 * Destroys the specified element of the specified list.
 * @n The destructor set for the list will be used to free the elements of the list.
 * @n If no one has been set, the free function will be used.
 * @param list The list containing the element.
 * @param element The element to destroy.
 * @todo Test the function.
 */
static void array_list_destroy_element (array_list list, void* element);

/**
 * Grows the end of the array of the specified list.
 * @param list
 * @param needed_increment
 * @retval 0
 * @retval 1
 * @todo Test the function.
 */
static unsigned int array_list_grow_at_end(array_list list, unsigned int needed_increment);

/**
 * Grows the front of the array of the specified list
 * @param list
 * @param needed_increment
 * @retval 0
 * @retval 1
 * @todo Test the function.
 */
static unsigned int array_list_grow_at_front(array_list list, unsigned int needed_increment);

/**
 * Grows the array at the specified position of the specified list
 * @param list
 * @param position
 * @param needed_increment
 * @retval 0
 * @retval 1
 * @todo Test the function.
 */
static unsigned int array_list_grow_for_insert(array_list list, unsigned int position, unsigned int needed_increment);

unsigned int array_list_add_element(array_list list, const void* element)
{
	unsigned int return_value = 1;

	/* Increases array capacity if it is full */
	if (list->size == list->array_capacity)
	{
		return_value = array_list_grow_at_end(list, 1);
	}
	/* If array is not full or increase succeed */
	if (return_value)
	{
		list->array[list->last_index++] = (void*) element;
		list->size++;
		return 1;
	}
	/* If an error occurred when increasing array capacity */
	else
	{
		return 0;
	}
}

unsigned int array_list_add_element_at(array_list list, unsigned int index, const void* element)
{
	unsigned int new_first;

	if (index > 0 && index < list->size)
	{
		new_first = list->first_index + index;
		/* If the array is full */
		if (list->size == list->array_capacity)
		{
			array_list_grow_for_insert(list, index, 1);
		}
		/* If adding in the first half of the array, moves all elements before index to one position left */
		else if ((index < list->size / 2 && list->first_index > 0) || list->last_index == list->array_capacity)
		{
			memmove(&(list->array[list->first_index - 1]), &(list->array[list->first_index]), sizeof(void*) * (index + 1));
			(list->first_index)--;
		}
		/* If adding in the second half of the array, move all elements after index to one position right */
		else
		{
			memmove(&(list->array[new_first + 1]), &(list->array[new_first]), sizeof(void*) * (list->last_index - new_first));
			(list->last_index)++;
		}
		list->array[new_first] = (void*) element;
		(list->size)++;
		return 1;
	}
	/* Insertion at the front of the list */
	else if (index == 0)
	{
		if (list->first_index == 0)
			array_list_grow_at_front(list, 1);
		list->array[--list->first_index] = (void*) element;
		(list->size)++;
		return 1;
	}
	/* Insertion at the end of the list */
	else if (index == list->size)
	{
		if (list->last_index == list->array_capacity)
			array_list_grow_at_end(list, 1);
		list->array[list->last_index++] = (void*) element;
		(list->size)++;
		return 1;
	}
	/* Out of bounds exception */
	else
		return 0;
}

static unsigned int array_list_calculate_increment(array_list list, unsigned int needed_increment)
{
	unsigned int calculated_increment;
	/* If the user specified a capacity_increment_value */
	if (list->capacity_increment != DEFAULT_CAPACITY_INCREMENT_FACTOR)
	{
		calculated_increment = list->capacity_increment;
		if (calculated_increment < needed_increment)
			calculated_increment = needed_increment;
	}
	else
	{
		calculated_increment = (int) ((float)list->array_capacity * list->capacity_increment_factor) - list->array_capacity;
		if (calculated_increment < needed_increment)
			calculated_increment = needed_increment;
		/* We ensure to increase the capacity with at least a value of 12 */
		if (calculated_increment < 12)
			calculated_increment = 12;
	}
	return calculated_increment;
}

void array_list_clear(array_list list)
{
	unsigned int index;

	if (list->size > 0)
	{
		for (index = list->first_index; index < list->last_index; index++)
		{
			array_list_destroy_element(list, list->array[index]);
			list->array[index] = NULL;
		}
		//memset(&(list->array[list->first_index]), (int) NULL, sizeof(void*) * list->size);
		list->first_index = 0;
		list->last_index = 0;
		list->size = 0;
	}
}

array_list array_list_clone(array_list list)
{
	array_list clone = (array_list) malloc(sizeof(struct array_list));
	if (clone != NULL)
	{
		memcpy(clone, list, sizeof(struct array_list));
		clone->array = (void**) malloc(sizeof(void*) * list->array_capacity);
		memcpy(clone->array, list->array, sizeof(void*) * list->array_capacity);
		return clone;
	}
	return NULL;
}

static unsigned int array_list_compare_elements(array_list list, const void* element1, const void* element2)
{
	if (list->elements_comparator == NULL)
	{
		if (element1 == element2)
			return 0;
		else if (element1 < element2)
			return -1;
		else 
			return 1;
	}
	else
	{
		return list->elements_comparator(element1, element2);
	}
}

unsigned int array_list_contains(array_list list, const void* element)
{
	unsigned int index;

	for (index = list->first_index; index < list->last_index; index++)
	{
		if (array_list_compare_elements(list, list->array[index],element) == 0)
			return 1;
	}
	return 0;
}

static void array_list_destroy_element(array_list list, void* element)
{
	if (list->element_destructor != NULL)
		list->element_destructor(element);
	else
		free(element);
}

void array_list_dispose(array_list list)
{
	unsigned int index;

	for (index = list->first_index; index < list->last_index; index++)
		array_list_destroy_element(list, list->array[index]);
	free(list->array);
	free(list);
}

void array_list_ensure_capacity(array_list list, unsigned int min_capacity)
{
	if (list->array_capacity < min_capacity)
	{
		if (list->first_index > 0)
			array_list_grow_at_front(list, min_capacity - list->array_capacity);
		else
			array_list_grow_at_end(list, min_capacity - list->array_capacity);
	}
}

int array_list_first_index_of(array_list list, const void* element)
{
	unsigned int index;

	for (index = list->first_index; index < list->last_index; index++)
	{
		if (array_list_compare_elements(list, list->array[index], element) == 0)
			return index;
	}
	return -1;
}

unsigned int array_list_get_capacity_increment(array_list list)
{
	return list->capacity_increment;
}

float array_list_get_capacity_increment_factor(array_list list)
{
	return list->capacity_increment_factor;
}

void* array_list_get_element_at(array_list list, unsigned int index)
{
	if (index < (list->size))
		return list->array[list->first_index + index];
	return NULL;
}

static unsigned int array_list_grow_at_end(array_list list, unsigned int needed_increment)
{
	unsigned int increment;
	unsigned int new_array_capacity;
	void** new_array;

	/** If the array is not full we move the elements at the front of the array */
	if (list->first_index >= needed_increment - (list->array_capacity - list->last_index))
	{
		if (list->size > 0)
		{
			memmove(list->array, &(list->array[list->first_index]), sizeof(void*) * list->size);
			memset(&(list->array[list->size]), (int) NULL, sizeof(void*) * list->array_capacity - list->size);
		}
		list->first_index = 0;
		list->last_index = list->size;
		return 1;
	}
	/* If the array is full we reallocate it */
	else
	{
		increment = array_list_calculate_increment(list, needed_increment);
		new_array_capacity = list->size + increment;
		new_array = (void**) realloc(list->array, sizeof(void*) * new_array_capacity);
		if (new_array == NULL)
			return 0;
		else
		{
			free(list->array);
			list->array = new_array;
			list->array_capacity = new_array_capacity;
			return 1;
		}
	}
}

static unsigned int array_list_grow_at_front(array_list list, unsigned int needed_increment)
{
	unsigned int increment;
	unsigned int new_array_capacity;
	void** new_array;
	unsigned int calc;

	calc = list->array_capacity - list->size;
	/* If the array is not full we move the elements at the end of the array */
	if (calc >= needed_increment)
	{
		if (list->size > 0)
		{
			memmove(&(list->array[calc]), &(list->array[list->first_index]), sizeof(void*) * list->size);
			memset(&(list->array[list->first_index]), (int) NULL, sizeof(void*) * (needed_increment - list->first_index));
		}
		list->first_index = calc;
		list->last_index = list->array_capacity;
		return 1;
	}
	/* If the array is full we reallocate it */
	else
	{
		increment = array_list_calculate_increment(list, needed_increment);
		new_array_capacity = list->size + increment;
		new_array = (void**) malloc(sizeof(void*) * new_array_capacity);
		if (new_array == NULL)
			return 0;
		else
		{
			if (list->size > 0)
			{
				memcpy(&(new_array[list->first_index + needed_increment - 1]), &(list->array[list->first_index]), sizeof(void*) * list->size);
			}

			list->first_index = needed_increment - 1;
			list->last_index = new_array_capacity;
			free(list->array);
			list->array = new_array;
			list->array_capacity = new_array_capacity;
			return 1;
		}
	}
}

static unsigned int array_list_grow_for_insert(array_list list, unsigned int position, unsigned int needed_increment)
{
	unsigned int increment;
	unsigned int new_array_capacity;
	void** new_array;

	increment = array_list_calculate_increment(list, needed_increment);
	new_array_capacity = list->size + increment;
	new_array = (void**) malloc(sizeof(void*) * new_array_capacity);
	if (new_array == NULL)
		return 0;
	else
	{
		memcpy(new_array, &(list->array[list->first_index]), sizeof(void*) * position);
		memcpy(&new_array[position + needed_increment], &(list->array[list->first_index + position]), sizeof(void*) * (list->size - (position + needed_increment)));
		free(list->array);
		list->array = new_array;
		list->first_index = 0;
		list->last_index = list->size + needed_increment;
		list->array_capacity = new_array_capacity;
		return 1;
	}
}

unsigned int array_list_is_empty(array_list list)
{
	return list->size == 0;
}

int	array_list_last_index_of (array_list list, const void* element)
{
	unsigned int index;
	unsigned int last_index = -1;

	for (index = list->first_index; index < list->last_index; index++)
	{
		if (array_list_compare_elements(list, list->array[index], element) == 0)
			last_index = index;
	}
	return last_index;
}

array_list array_list_new(unsigned int initial_capacity, unsigned int capacity_increment, const float capacity_increment_factor, comparator_t elements_comparator, destructor_t element_destructor)
{
	array_list list = (array_list) malloc(sizeof(struct array_list));

	if (list != NULL)
	{
		list->first_index = 0;
		list->last_index = 0;
		list->array_capacity = ((initial_capacity == (unsigned int) NULL) || (initial_capacity == 0)) ? DEFAULT_INITIAL_CAPACITY : initial_capacity;
		list->size = 0;
		list->array = (void**) calloc(list->array_capacity, sizeof(void*));
		//list->array = (void**) malloc(sizeof(void*) * list->array_capacity);
		//memset(list->array, (int) NULL, sizeof(void*) * list->array_capacity);
		list->capacity_increment = ((capacity_increment == (unsigned int) NULL) || (capacity_increment == 0)) ? DEFAULT_CAPACITY_INCREMENT : capacity_increment;
		list->capacity_increment_factor = ((capacity_increment == (unsigned int) NULL) || (capacity_increment == 0)) ? DEFAULT_CAPACITY_INCREMENT_FACTOR : capacity_increment_factor;
		list->elements_comparator = elements_comparator;
		list->element_destructor = element_destructor;
	}

	return list;
}

unsigned int array_list_quick_sort(array_list list)
{
	if (list->elements_comparator != NULL)
	{
		qsort(&(list->array[list->first_index]), list->size, sizeof(void*), list->elements_comparator);
		return 1;
	}
	return 0;
}

unsigned int array_list_remove_all_occurrences(array_list list, const void* element)
{
	return 0;
}

void* array_list_remove_at(array_list list, unsigned int index)
{
	unsigned int element_index;
	void* result;

	if (index < list->size)
	{
		/* Removes the last element */
		if (index == list->size - 1)
		{
			result = list->array[--(list->last_index)];
			list->array[list->last_index] = NULL;
		}
		/* Removes the first element */
		else if (index == 0)
		{
			result = list->array[(list->first_index)];
			list->array[(list->first_index)++] = NULL;
		}
		/* Removes any element */
		else
		{
			element_index = list->first_index + index;
			result = list->array[element_index];
			/* In the first half of the array, moves all elements before the removed element of one to left */
			if (index < list->size / 2)
			{
				memmove(&(list->array[list->first_index + 1]), &(list->array[list->first_index]), sizeof(void*) * index);
				list->array[(list->first_index)++] = NULL;
			}
			/* In the second half of the array, moves all elements after the removed element of one to right */
			else
			{
				memmove(&(list->array[element_index]), &(list->array[element_index + 1]), sizeof(void*) * (list->size + index));
				list->array[--(list->last_index)] = NULL;
			}
		}
		/* If list becomes empty */
		(list->size)--;
		if (list->size == 0)
		{
			list->first_index = 0;
			list->last_index = 0;
		}
		return result;
	}
	else
		return NULL;
}

unsigned int array_list_remove_first_occurrence(array_list list, const void* element)
{
	int first_index_of_element = array_list_first_index_of(list, element);
	if (first_index_of_element >= 0)
	{
		array_list_remove_at(list, first_index_of_element);
		return 1;
	}
	return 0;
}

void array_list_remove_range(array_list list, unsigned int from_index, unsigned int to_index)
{
	unsigned int index;
	unsigned int first_removed_index;
	unsigned int calc;
	unsigned int range;

	if (from_index <= to_index && to_index <= list->size)
	{
		if (from_index == to_index)
			return;
		range = to_index - from_index;
		first_removed_index = list->first_index + from_index;
		if (range == list->size)
		{
			for (index = first_removed_index; index < list->last_index; index++)
			{
				array_list_destroy_element(list, list->array[index]);
				list->array[index] = NULL;
			}
			list->last_index = first_removed_index;
		}
		else if (from_index == 0)
		{
			calc = list->first_index + to_index;
			for (index = list->first_index; index < calc; index++)
			{
				array_list_destroy_element(list, list->array[index]);
				list->array[index] = NULL;
			}
			list->first_index = calc;
		}
		else
		{
			for (index = first_removed_index; index < first_removed_index + range; index++)
			{
				array_list_destroy_element(list, list->array[index]);
				list->array[index] = NULL;
			}
			memmove(&(list->array[first_removed_index]), &(list->array[list->first_index + to_index]), sizeof(void*) * (list->size - to_index));
			list->last_index -= range;
		}
		list->size -= range;
	}
}

void array_list_set_capacity_increment(array_list list, unsigned int capacity_increment)
{
	list->capacity_increment = capacity_increment;
}

void array_list_set_capacity_increment_factor(array_list list, const float capacity_increment_factor)
{
	list->capacity_increment_factor = capacity_increment_factor;
}

void array_list_set_comparator(array_list list, comparator_t elements_comparator)
{
	list->elements_comparator = elements_comparator;
}

void array_list_set_destructor(array_list list, destructor_t element_destructor)
{
	list->element_destructor = element_destructor;
}

void* array_list_set_element_at(array_list list, unsigned int index, const void* element)
{
	void* result;

	if (index < list->size)
	{
		result = list->array[list->first_index + index];
		list->array[list->first_index + index] = (void*) element;
		return result;
	}
	return NULL;
}

unsigned int array_list_size(array_list list)
{
	return list->size;
}

array_list array_list_sublist(array_list list, unsigned int from_index, unsigned int to_index)
{
	return NULL;
}

void** array_list_to_array(array_list list)
{
	//void** array = (void**) malloc(sizeof(void*) * list->size);
	void** array = (void**) calloc(list->size, sizeof(void*));
	if (array != NULL)
	{
		memcpy(array, &(list->array[list->first_index]), sizeof(void*) * list->size);
	}
	return array;
}

char* array_list_to_string(array_list list)
{
	return "Not implemented yet";
}

void array_list_trim_to_size(array_list list)
{
	void** temp = list->array;
	list->array = array_list_to_array(list);
	free(temp);
}
